package com.lyt.springboot.util.algorithm;

import java.util.*;

public class S22 {
    public static void main(String[] args) {
        S22 s22 = new S22();
//        int[] arr = {2, 2, 3, 4, 3};
//        s22.maxLength1(arr);
        int[] arr = {1, 2, 3, 4, 5, 6};
        int size = 3;
        s22.maxInWindows1(arr,size);
    }
    public ArrayList<Integer> maxInWindows1(int[] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        if (size > num.length || size <= 0) {
            return list;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < num.length; i++) {
            queue.add(num[i]);
            if(i>=size -1) {
                list.add(Collections.max(queue));
                queue.poll();
            }
        }
        return list;
    }

    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        if (size > num.length || size <= 0) {
            return list;
        }
        int left = 0;
        int right = size-1;
        while(right<num.length) {
            int max = getMax(left,right,num);
            left++;
            right++;
            list.add(max);
        }
        return list;
    }
    public int getMax(int left,int right,int[] num) {
        int max = num[left];
//        while(left<right) {
//            if(num[left]<num[right]) {
//                max = num[right];
//            }
//            left++;
//            right--;
//        }
        for (int i = left; i <=right ; i++) {
            if(max<num[i]) {
               max = num[i];
            }
            
        }
        return max;
    }

    public int maxLength(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }
        return set.size();   //出现边界问题
    }

    public int maxLength1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;

        }
        int res = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int c : arr) {
            while (queue.contains(c)) {
                //如果有重复的，队头出队
                queue.poll();
            }
            //添加到队尾
            queue.add(c);
            res = Math.max(res, queue.size());
        }
        int size = queue.size();
        return res;
    }

    // 双指针----》类比队列  + set
    // left 队尾  right队首
    public int maxLength2(int[] arr) {
        int left = 0;
        int right = 0;
        int max = 0;
        HashSet<Integer> set = new HashSet<>();
        while (right < arr.length) {
            if (set.contains(arr[right])) {
                set.remove(arr[left++]);
            } else {
                set.add(arr[right++]);
                max = Math.max(max, set.size());
            }
        }
        return max;
    }

    public String minWindow(String S, String T) {
        int left = 0;
        int right = S.length() - 1;
        while (left < right) {
        }
        return null;
    }

}
